// ml:run = $bin < input
// ml:opt = 0
// ml:ccf += -g
#include <iostream>
#include <vector>

using ll = long long;
ll const mo = 2147493647;

struct matrix
{
	using value_type = long long;
	using row_type = std::vector<value_type>;

	matrix(int ro, int co)
	{
		mat.resize(ro);
		for (auto & i : mat) i.resize(co);
	}

	matrix(int n) : matrix(n, n)
	{
		for (int i = 0; i < n; i++) mat[i][i] = 1;
	}

	matrix() = default;

	int row() const { return mat.size(); }
	int col() const { return mat[0].size(); }

	row_type       & operator[](int x)       { return mat[x]; }
	row_type const & operator[](int x) const { return mat[x]; }

	private:
	std::vector<row_type> mat;
};

matrix operator*(matrix const & a, matrix const & b)
{
	int n = a.row(), m = b.col(), t = a.col();
	matrix r(n, m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < t; k++)
				r[i][j] = (r[i][j] + (a[i][k] * b[k][j]) % mo) % mo;
	return r;
}

matrix quick_pow(matrix const & a, long long b)
{
	if (!b) return matrix(a.row());

	matrix ret = quick_pow(a, b / 2);
	ret = ret * ret;
	if (b & 1) ret = ret * a;
	return ret;
}


ll n, ta, tb;

int main()
{
    std::ios_base::sync_with_stdio(false);
    int T; std::cin >> T;
    while (T--) {
        std::cin >> n >> ta >> tb;
        if (n == 1) { std::cout << ta << "\n"; continue; }
        if (n == 2) { std::cout << tb << "\n"; continue; }
        matrix a(7, 7);
        a[0][0] = 1; a[0][1] = 2; a[0][2] = 1;
        a[1][0] = 1;
        a[2][0] = 0; a[2][1] = 0; a[2][2] = 1; a[2][3] = 4; a[2][4] = 6; a[2][5] = 4; a[2][6] = 1;
        a[3][0] = 0; a[3][1] = 0; a[3][2] = 0; a[3][3] = 1; a[3][4] = 3; a[3][5] = 3; a[3][6] = 1;
        a[4][0] = 0; a[4][1] = 0; a[4][2] = 0; a[4][3] = 0; a[4][4] = 1; a[4][5] = 2; a[4][6] = 1;
        a[5][0] = 0; a[5][1] = 0; a[5][2] = 0; a[5][3] = 0; a[5][4] = 0; a[5][5] = 1; a[5][6] = 1;
        a[6][0] = 0; a[6][1] = 0; a[6][2] = 0; a[6][3] = 0; a[6][4] = 0; a[6][5] = 0; a[6][6] = 1;

        matrix init(7, 1);
        init[0][0] = tb; init[1][0] = ta; init[2][0] = 81; init[3][0] = 27; init[4][0] = 9; init[5][0] = 3; init[6][0] = 1;

        a = quick_pow(a, n - 2);
        init = a * init;
        std::cout << init[0][0] << "\n";
    }
}

